package com.atguigu.hashtable;

import java.util.Scanner;

/**
 * @author 龍
 * 哈希表实现google上机问题:
 */
public class HashTableDemo {
    public static void main(String[] args) {
        HashTab hashTab = new HashTab(7);
        //写一个简单的测试
        char key;
        Scanner scanner = new Scanner(System.in);
        while (true){
            System.out.println("add--a:添加雇员");
            System.out.println("list--l:显示雇员");
            System.out.println("findEmpById--f:根据id获取员工信息");
            System.out.println("delEmpById--d:根据id删除员工信息");
            System.out.println("exit--e:退出系统！！！");
            key=scanner.next().charAt(0);
            switch (key){
                case 'a':
                    System.out.println("请输入id：");
                    int id=scanner.nextInt();
                    System.out.println("请输入姓名：");
                    String name=scanner.next();
                    Emp emp=new Emp(id,name);
                    hashTab.add(emp);
                    break;
                case 'l':
                    hashTab.list();
                    break;
                case 'f':
                    System.out.println("请输入需要查询的员工的id：");
                    int empId=scanner.nextInt();
                    hashTab.findEmpById(empId);
                    break;
                case 'd':
                    System.out.println("请输入需要删除的员工的id：");
                    int delEmpId=scanner.nextInt();
                    hashTab.delEmpById(delEmpId);
                    break;
                default:break;
            }
        }

    }
}
/**
 * 创建HashTab 管理多条链表
 */
class HashTab{
    private EmpLinkedList[] empLinkedListArray;
    private int size;

    public HashTab(int size){
        this.size=size;
        //初始化empLinkedListArray
        empLinkedListArray=new EmpLinkedList[size];
        //需要初始化每一条链表
        for (int i = 0; i <size ; i++) {
            empLinkedListArray[i]=new EmpLinkedList();
        }
    }

    /**
     * 添加的方法
     * @param emp：待添加的员工的信息
     */
    public void add(Emp emp){
        //根据员工的id，得到该员工应该添加到哪一条链表
        int empLinkedListNo = hashFun(emp.id);
        //将emp添加到对应的链表中去
        empLinkedListArray[empLinkedListNo].add(emp);

    }
    /**
     * 遍历的方法
     */
    public void list(){
        for (int i = 0; i < size; i++) {
            empLinkedListArray[i].list(i);
        }
    }
    /**
     * 编写一个散列函数，简单的取模法
     */
    public int hashFun(int id){
        return id % size;
    }
    /**
     * 根据id获取员工信息的方法
     */
    public void findEmpById(int id){
        //使用散列函数确定是哪一条链表
        Emp emp = empLinkedListArray[hashFun(id)].findEmpById(id);
        if (emp!=null){
            System.out.println("在第"+hashFun(id)+"条链表，信息为："+"id="+emp.id+"\t"+"name="+emp.name);
        }else {
            System.out.println("不存在这个雇员！！！");
        }
    }
    /**
     * 根据id删除雇员
     */
    public void delEmpById(int id){
        empLinkedListArray[hashFun(id)].delEmpById(id);
    }


}

/**
 * 创建雇员
 */
class Emp{
    public int id;
    public String name;
    public Emp next;
    public Emp(int id,String name){
        super();
        this.id=id;
        this.name=name;
    }
}
/**
 * 创建EmpLinkedList链表,表示一条链表
 */
class EmpLinkedList{
    /**
     * 需要一个头指针，指向第一个emp。
     */
    private Emp head;

    /**
     * 假定添加雇员列表的时候，id是自增长的，即id的分配钟使从小到大。因此直接添加到本列表的最后即可
     * @param emp：需要添加的雇员
     */
    public void add(Emp emp){
        if (head==null){
            head=emp;
            return;
        }
        Emp curEmp=head;
        while (true){
            if (curEmp.next==null){
                break;
            }
            curEmp=curEmp.next;
        }
        //退出时直接将emp加入链表
        curEmp.next=emp;
    }
    /**
     * 遍历雇员信息
     */
    public void list(int no){
        if (head==null){
            System.out.println("第"+no+"条链表为空");
            return;
        }
        System.out.println("************第"+no+"条链表的信息*************");
        Emp curEmp=head;
        while(true){
            System.out.println("id="+curEmp.id+"\t"+"name="+curEmp.name);
            if (curEmp.next==null){
                break;
            }
            curEmp=curEmp.next;
        }
        System.out.println();
    }

    /**
     * 根据id查找员工
     * @param id：员工id
     * @return : 返回查询的员工
     */
    public Emp findEmpById(int id){
        if (head==null){
            System.out.println("链表为空");
            return null;
        }
        Emp curEmp=head;
        while (true){
            if (curEmp.id==id){
                break;
            }
            if (curEmp.next==null){
                curEmp=null;
                break;
            }
            curEmp=curEmp.next;
        }
        return curEmp;
    }
    /**
     * 根据id删除员工
     */
    public void delEmpById(int id){
        if (head==null){
            System.out.println("链表为空，此雇员不存在！！！");
            return;
        }
        if (head.id==id){
            if (head.next!=null){
                head=head.next;
                System.out.println("删除成功");
                return;
            }
        }
        Emp curEmp=head;
        boolean flag=false;
        while (true){
            if (curEmp.next==null){
                break;
            }
            if (curEmp.next.id==id){
                flag=true;
                break;
            }
            curEmp=curEmp.next;
        }
        if (flag){
            curEmp.next=curEmp.next.next;
            System.out.println("删除该雇员成功！");
        }else {
            System.out.println("该雇员不存在");
        }
    }

}


